package com.zk.algorithm;

import com.zk.algorithm.bean.Graph;

import java.util.LinkedList;

/**
 * DFS 算法
 * https://en.wikipedia.org/wiki/Topological_sorting#Algorithms
 *
 * 有向无环图（DAG）才有拓扑排序
 *
 *
 * - Kahn 算法
 * - DFS 深度优先搜索算法 (回溯)
 */
public class TopologicalSort {

    public static void main(String...args) {
        Graph graph = new Graph(6);
        graph.addEdge(1, 3);
        graph.addEdge(1, 5);
        graph.addEdge(4, 5);
        graph.addEdge(2, 3);

        TopologicalSort topologicalSort = new TopologicalSort();
        topologicalSort.topoSortByKahn(graph);
    }

    /**
     * 入度为 0 的放入队列
     *
     * 1 -> 3 -> 5
     * 4 -> 5
     * 2 -> 3
     *
     * DFS 算法的时间复杂度我们之前分析过。
     * 每个顶点被访问两次，每条边都被访问一次，所以时间复杂度也是 O(V+E)。
     *
     * @param graph
     */
    public void topoSortByKahn(Graph graph) {
        int[] inDegree = new int[graph.v]; // 统计每个顶点的入度

        for (int i = 0; i < graph.v; ++i) {
            for (int j = 0; j < graph.adj[i].size(); ++j) {
                int w = graph.adj[i].get(j); // i->w
                inDegree[w]++;
            }
        }

        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < graph.v; ++i) {
            if (inDegree[i] == 0)
                queue.add(i);
        }

        // 1 -> 3 -> 5
        // 4 -> 5
        while (!queue.isEmpty()) {
            int i = queue.remove();
            System.out.print("->" + i);

            for (int j = 0; j < graph.adj[i].size(); ++j) {
                // 3 -> 5
                int k = graph.adj[i].get(j);
                inDegree[k]--;

                if (inDegree[k] == 0)
                    queue.add(k);
            }
        }
    }

    public void topoSortByDFS(Graph graph) {
        // 先构建逆邻接表，边 s->t 表示，s 依赖于 t，t 先于 s
        LinkedList<Integer> inverseAdj[] = new LinkedList[graph.v];
        for (int i = 0; i < graph.v; ++i) { // 申请空间
            inverseAdj[i] = new LinkedList<>();
        }

        for (int i = 0; i < graph.v; ++i) { // 通过邻接表生成逆邻接表
            for (int j = 0; j < graph.adj[i].size(); ++j) {
                int w = graph.adj[i].get(j); // i->w
                inverseAdj[w].add(i); // w->i
            }
        }

        boolean[] visited = new boolean[graph.v];
        for (int i = 0; i < graph.v; ++i) { // 深度优先遍历图
            if (visited[i] == false) {
                visited[i] = true;
                dfs(i, inverseAdj, visited);
            }
        }
    }

    private void dfs(int vertex, LinkedList<Integer> inverseAdj[], boolean[] visited) {
        for (int i = 0; i < inverseAdj[vertex].size(); ++i) {
            int w = inverseAdj[vertex].get(i);
            if (visited[w] == true) continue;
            visited[w] = true;
            dfs(w, inverseAdj, visited);
        } // 先把 vertex 这个顶点可达的所有顶点都打印出来之后，再打印它自己
        System.out.print("->" + vertex);
    }

}
